// LeetCode 主站 Problem Nr. 92: 反转链表 II

/*
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
	输入：head = [1,2,3,4,5], left = 2, right = 4
	输出：[1,4,3,2,5]
示例 2：
	输入：head = [5], left = 1, right = 1
	输出：[5]

提示：
    链表中节点数目为 n
    1 <= n <= 500
    -500 <= Node.val <= 500
    1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	return method1(head, left, right)
}

func reverse(node *ListNode) {
	var pointer1 *ListNode = nil
	pointer2 := node
	for pointer2 != nil {
		next := pointer2.Next
		pointer2.Next = pointer1
		pointer1 = pointer2
		pointer2 = next
	}
}

func method1(head *ListNode, left, right int) *ListNode {
	pointer1 := &ListNode{
		Val: -1,
		Next: head,
	}

	pointer2 := pointer1
	for i := 0; i < left-1; i++ {
		pointer2 = pointer2.Next
	}

	pointer3 := pointer2
	for i := 0; i < right-left+1; i++ {
		pointer3 = pointer3.Next
	}

	pointer4 := pointer2.Next
	pointer5 := pointer3.Next

	pointer2.Next = nil
	pointer3.Next = nil

	reverse(pointer4)

	pointer2.Next = pointer3
	pointer4.Next = pointer5

	return pointer1.Next
}

func method2(head *ListNode, left, right int) *ListNode {
	sentinel := &ListNode{
		Val: -1,
		Next: head,
	}

	previous := sentinel
	for i := 0; i < left-1; i++ {
		previous = previous.Next
	}

	current := previous.Next
	for i := 0; i < right-left; i++ {
		next := current.Next
		current.Next = next.Next
		next.Next = previous.Next
		previous.Next = next
	}

	return sentinel.Next
}